/*
#Copyright (c) 2013, Philippe Bordron <philippe.bordron@gmail.com>
#
# This file is part of SIPPER.
#
# DCC is free software: you can redistribute it and/or modify
# it under the terms of the GNU LESSER GENERAL PUBLIC LICENSE as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# DCC is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU LESSER GENERAL PUBLIC LICENSE for more details.
#
# You should have received a copy of the GNU LESSER GENERAL PUBLIC LICENSE
# along with SIPPER.  If not, see <http://www.gnu.org/licenses/>
*/
package combi.graph.algo;

import combi.graph.Kpaths;
import combi.graph.Mask;
import combi.graph.PrefixTree;
import combi.graph.PrefixTreeNode;
import combi.sipper.io.IOSimpleGraph;

import java.io.IOException;
import java.util.*;

import org.jgrapht.DirectedGraph;
import org.jgrapht.GraphPath;
import org.jgrapht.alg.DijkstraShortestPath;
import org.jgrapht.graph.DefaultDirectedWeightedGraph;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.DirectedMaskSubgraph;
import org.jgrapht.graph.GraphPathImpl;

/***
 * TODO Need to be rewritten
 * @author philippebordron
 *
 * @param <V> vertices
 * @param <E> edges
 */


public class Ksp_Yen<V,E> implements Runnable{

	private DirectedGraph<V, E> graph;
	private V src;
	private V dest;
	private int k;
	
	private Map<List<E>, Double> cheminsEtScore = new HashMap<List<E>, Double>(); // score des chemins
	
	
	private List<List<E>> paths;

	public Ksp_Yen(DirectedGraph<V, E> graph, V src, V dest, int k)
	{
		this.graph = graph;
		this.src = src;
		this.dest = dest;
		this.k = k;
		this.cheminsEtScore = new HashMap<List<E>, Double>();
	}

	public void clear()
	{
		cheminsEtScore.clear();
	}


	public void run() {
		DijkstraShortestPath<V,E> dijkstra = new DijkstraShortestPath<V,E>(graph, src, dest);
		PrefixTree<E> chemins = new PrefixTree<E>();
		List<List<E>> candidats = new ArrayList<List<E>>(k);
		Map<List<E>, Double> scoreCandidats = new HashMap<List<E>, Double>(); // score des chemins (candidats)
		List<E> path = dijkstra.getPathEdgeList();
		//System.err.println(path);
		//graphe modifie pour les besoins de l'algo
		Mask<V,E> maskModdedGraph = new Mask<V,E>();
		DirectedMaskSubgraph<V, E> moddedGraph = new DirectedMaskSubgraph<V, E>(graph, maskModdedGraph);
		int nb = 0; // nombre de solutions explor�es
		if (path != null)
		{ 
			candidats.add(path);
			//System.err.println("debut");
			scoreCandidats.put(path, dijkstra.getPathLength());
			List<E> cheminEnCours;
			//System.err.println(candidats);
			while(!candidats.isEmpty() && nb < (k -1))
			{
				cheminEnCours = candidats.get(0); // ajout du plus petit chemin candidat � l'ensemble des solutions
				cheminsEtScore.put(cheminEnCours, scoreCandidats.get(cheminEnCours));
				candidats.remove(0); // retrait de ce chemin des candidats.
				//System.err.println((nb+1) + "-ieme plus court chemin : " + scoreCandidats.get(cheminEnCours) + ":" + convertEdgesPath2NodesPath(cheminEnCours));
				PrefixTreeNode<E> devEdge = chemins.addSequence(cheminEnCours); //ajout du chemin et obtenition de l'arc � la suite duquel a lieu la d�viation
				//System.err.print("Point de d�viation : " + devEdge.getVal() + "\t");
				nb++;
				LinkedList<E> prefixe = new LinkedList<E>();
				double scorePrefixe = 0.0;
				ListIterator<E> suffixe;

				//2.2a- pr�paration de la recherche de plus courts sous chemins.
				V devNode = null; // noeud de d�viation sur le chemin en court.
				if(devEdge == null || devEdge.getVal() == null)
				{
					// pas d'arc : point de deviation = src.
					devNode = src;
					//devEdge = chemins.getSon(cheminEnCours.get(0));// deviation a la racine de l'arbre.
					devEdge = chemins.getRoot();
					suffixe = cheminEnCours.listIterator();
				}
				else
				{
					//pt de deviation = destination de l'arc.
					devNode = graph.getEdgeTarget(devEdge.getVal());
					boolean fini = false;
					//?
					suffixe = cheminEnCours.listIterator(); //ici pour ne pas recalculer la position du pt de deviation.
					//on calcule le poids du prefixe (possible de s'en passer plus tard avec asso score � arbre prefixe?)
					while(suffixe.hasNext() && !fini)
					{
						E n = suffixe.next();
						fini = devEdge.getVal() == n;
						if (!fini)
						{
							prefixe.addLast(n);
							scorePrefixe = scorePrefixe + graph.getEdgeWeight(n);
						}
						maskModdedGraph.addVertex(graph.getEdgeSource(n)); // noeud a retirer
					}
					prefixe.addLast(devEdge.getVal());
					scorePrefixe = scorePrefixe + graph.getEdgeWeight(devEdge.getVal());
				}
				//System.err.println("prefixe : " + prefixe);
				E tmp = suffixe.next();
				///System.err.println(tmp);
				PrefixTreeNode<E> edgeTemp = devEdge;
				suffixe.previous();
				V srcTemp = devNode;
				LinkedList<E> candidatPotentiel;
				do{
					if (edgeTemp.getVal() == null) // cas racine
					{
						srcTemp = devNode;
					}
					else
					{
						srcTemp = graph.getEdgeTarget(edgeTemp.getVal());
						//scorePrefixe = scorePrefixe + graph.getEdgeWeight(edgeTemp.getVal());
					}
					for (PrefixTreeNode<E> fils : edgeTemp.getChilds())
					{
						maskModdedGraph.addEdge(fils.getVal());
					}
					///	System.err.println("*****");
					///System.err.println("�tape : " + etape++);
					///System.err.println("arc d'attaque : " + edgeTemp.getVal());
					//System.err.println("sommet source du sous-graphe : " + srcTemp);
					///System.err.println("fils : " + edgeTemp.getChilds());
					//System.err.println(graph);
					//retrait des voisins d�j� utilis�s � partir de ce pr�fixe.
					///System.err.println("Sommets retir�s : " + removedNodes);
					//recherche du plus court chemin entre srcTemp et dest.
					dijkstra = new DijkstraShortestPath<V,E>(moddedGraph, srcTemp, dest);
					List<E> subPath = dijkstra.getPathEdgeList();
					double scoreSubPath;
					//System.err.println("plus court sous-chemin entre " + srcTemp + " et " + dest + " : " + subPath);
					if(subPath != null)
					{
						scoreSubPath = dijkstra.getPathLength();
						candidatPotentiel = new LinkedList<E>(prefixe);
						///System.err.println("delta : " + delta);
						candidatPotentiel.addAll(subPath);
						candidats.add(candidatPotentiel);
						//System.err.println("nouveau candidat : " + prefixe + subPath + " = " + convertEdgesPath2NodesPath(candidatPotentiel));
						double score = scorePrefixe + scoreSubPath;
						scoreCandidats.put(candidatPotentiel, score);	
					}


					//preparation etape suivante
					tmp = suffixe.next();
					prefixe.addLast(tmp);
					scorePrefixe = scorePrefixe + graph.getEdgeWeight(tmp);
					//System.err.println(tmp);
					edgeTemp = edgeTemp.getSon(tmp);
					maskModdedGraph.addVertex(srcTemp);
				}while(!edgeTemp.isLeaf());

				// rajout des �l�ments supprim�s
				maskModdedGraph.clear();
				
				//scoreCandidats.remove(cheminEnCours);
				Collections.sort(candidats, new CompareCandidats<List<E>>(scoreCandidats));
				///System.err.println("candidats : " + candidats);
				///System.err.println("-----------------------");
			}

			// sorti de la boucle tq
			//if (!candidats.isEmpty())
			//{
			//	chemins.addSequence(candidats.get(0));
			//}
		}
		paths = new LinkedList<List<E>>(chemins.toPaths());
		if (!candidats.isEmpty())
		{
			paths.add(candidats.get(0));
			cheminsEtScore.put(candidats.get(0), scoreCandidats.get(candidats.get(0)));	
		}
		Collections.sort(paths, new CompareCandidats<List<E>>(cheminsEtScore));
		candidats.clear();
		scoreCandidats.clear();
	}


	public Kpaths<V,E> getPaths()
	{
		return pathsToKPaths(paths);
	}
	
	public double getScoreChemin(List<DefaultWeightedEdge> path)
	{
		return cheminsEtScore.get(path);
	}
	
	public List<V> convertEdgesPath2NodesPath(List<E> edgesPath)
	{
		List<V> nodesPath = new LinkedList<V>();
		if (! edgesPath.isEmpty())
		{
			nodesPath.add(graph.getEdgeSource(edgesPath.get(0)));
			for (E e : edgesPath)
			{
				nodesPath.add(graph.getEdgeTarget(e));
			}
		}
		return nodesPath;
	}


	public class CompareCandidats<T> implements Comparator<T>
	{

		private Map<T, Double> scores;

		public CompareCandidats(Map<T, Double> scoreCandidats)
		{
			this.scores = scoreCandidats;
		}

		public int compare(T o1, T o2) {
			if (scores.get(o1) - scores.get(o2) >0)
			{
				return 1;
			}
			if (scores.get(o1) - scores.get(o2) <0)
			{
				return -1;
			}
			return 0;

		}
	}
	
	public static List<DefaultWeightedEdge> cut (List<DefaultWeightedEdge> l)
	{
		l.remove(l.size()-1);
		l.remove(0);
		return l;
	}
	
	public Kpaths<V, E> pathsToKPaths(Collection<List<E>> paths)
	{
		Kpaths<V, E> result = new Kpaths<V, E>(paths.size());
		for (List<E> l : paths)
		{
			result.add(edgeListToGraphPath(l));
		}
		return result;
	}
	
	
	public GraphPath<V, E> edgeListToGraphPath(List<E> l)
	{
		GraphPath<V, E> result = new GraphPathImpl<V,E>(graph, src, dest, l, cheminsEtScore.get(l));
		return result;
	}
	
	public static void main(String[] argv)
	{
		try {
			DefaultDirectedWeightedGraph<Integer, DefaultWeightedEdge> graph = IOSimpleGraph.load(argv[0]);
			Integer src = Integer.parseInt(argv[1]);
			Integer dest = Integer.parseInt(argv[2]);
			int k = Integer.parseInt(argv[3]);
			long oldtime = System.currentTimeMillis();
			System.out.println("Loading graph from the file " + argv[0]);
			Ksp_Yen<Integer, DefaultWeightedEdge> algo = new Ksp_Yen<Integer, DefaultWeightedEdge>(graph, src, dest, k);
			long newtime = System.currentTimeMillis();
			System.out.println("the process tooks " + (newtime - oldtime) + "ms");
			oldtime = newtime;
			System.out.println("Computation of the "+ k + " shortest loopless paths from " + src + " to " + dest);
			algo.run();
			newtime = System.currentTimeMillis();
			System.out.println("the process tooks " + (newtime - oldtime) + "ms");
			oldtime = newtime;
			System.out.println("Results listing:");
			for (GraphPath<Integer, DefaultWeightedEdge> p : algo.getPaths())
			{
				System.out.println(p.getWeight() + " :"+ p.toString().replace("]","").replace("["," "));
			}
			newtime = System.currentTimeMillis();
			System.out.println("the process tooks " + (newtime - oldtime) + "ms");
			oldtime = newtime;
			//System.out.println(algo.getPaths().toString().replace("], ","\n").replace("]]","\n").replace("[", ""));
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}
